COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.device xgp
C00004 00003	.every heading()
C00006 00004	.s Goals
C00010 00005	.s Work Plan
C00014 00006	.ss Crossbar Switch Design
C00019 00007	.s Coordination and Reporting
C00022 00008	.app SAIL Background in System Development
C00030 00009	.bib
C00033 00010	.next page s Budget
C00041 ENDMK
C⊗;
.device xgp
.if xcribl then start "xgp"
.require "bask.pub[sub,sys]" source_file;
.font 5 "metlb"; font 6 "metmb";
. end "xgp";
.sides←1;
.require "twocol.pub[sub,sys]" source_file;
.macro sskip	⊂skip(if lines<15 then 200 else 2)⊃;	<< section skip control >>
.macro appskip	⊂skip 200⊃;		<< appendix skip >>
.if ¬xcribl then start "tty"
.    page frame 52 high 72 wide;
.    title area heading lines 1 to 3
.    area text lines 4 to 52;
.    end "tty";
.
.MACRO BC ⊂ BEGIN PREFACE 0; INDENT 1,4; CRBREAK nojust ⊃
.
.MACRO BS ⊂ BEGIN PREFACE 0; INDENT 1,4; nojust ⊃
.
.MACRO IB ⊂ turn on "%";
.AT """" ⊂ (IF THISFONT=1 THEN "%3" ELSE "%1"); ⊃
.AT "<" ⊂ "%2" ⊃;  AT ">" ⊂ "%1" ⊃;
. ⊃

.MACRO BIB  ⊂  CB(References);
.	BEGIN INDENT 0,3; NOJUST; IB;
.	AT "AIM-" ⊂ "Stanford AI Memo AαIαMα-" ⊃;
.	COUNT exref TO 200
.	AT "⊗" ⊂ IF LINES<3 THEN NEXT COLUMN; NEXT EXREF; ("["&EXREF&"]  ") ⊃
.	⊃
.SECNAME←"";
.portion some; place text;
.every heading();
.onecol;
.begin "cover"
.center; select 6;
Octoberr 1978


Proposal to

%5University of California
Lawrence Livermore Laboratory%6

for design of

%5An Operating System for the S-1 Computer%6
.skip 2
John McCarthy, Professor of Computer Science
Principal Investigator
.skip 10;
Abstract
.skip
.begin fill;
The Stanford Artificial Intelligence Laboratory proposes to participate in
the Lawrence Livermore Laboratory program for development of the S-1
computer system by designing and developing an
operating system.  This proposal covers a one-year period beginning 1 January 1979.
.end
.skip 10
%5Computer Science Department
Stanford University
.end "cover"
.every heading(,"S-1 Proposal",{page});
.count page;
.if xcribl then twocol;
.s Goals

Building on a substantial background in computer timesharing system development
(see Appendix A), the Stanford Artificial Intelligence Laboratory
(SAIL) proposes to participate in the Lawrence Livermore Laboratory (LLL)
program for development of the S-1 computer system by designing certain elements
and developing an efficient operating system over a period of three years.
This proposal covers the first 9 months' work.


The proposed work will have the following subgoals:

1) Design and begin development of an operating sysem for both single and
multiprocessor S-1 computer configurations with dedicated disk systems.
This system will provide efficient resource allocation for configurations
of 1 to 32 processors and will include user interactive facilities that
are optimized for display terminals, though teleprinter terminals will
also be supported.  In addition to the operating system, a number of
utility programs will be developed, including text editors, file
management programs, compilers, and debuggers.

SAIL recognizes that the S-1 Project requires an evolving operating system
for the various computer configurations it is creating, and will undertake
to create an operating system that will have some minimal capability early
in the effort, growing thereafter in capability in frequent increments.

2)  Based on work done in pursuit of the first subgoal, recommend
specific equipment characteristics needed to support efficient
operation.  This particularly includes the manner in which
secondary memories and peripherals will connect to various S-1
system configurations.

3) Support S-1 Project hardware development, in fashions and to extents
mutualy agreed upon by cognizant SAIL and LLL staff.  During the period of
this initial proposal such support activity will include
detailed design of the crossbar switch for the first S-1 multiprocessor
configuration and the post-construction debugging and documentation of
this hardware module.

.s Work Plan
.ss Operating System Development

The operating system to be developed will exploit the full suite of
capabilities of multiprocessor S-1 configurations and will use the better
features of existing timesharing systems, such as Unix, Multics, TOPS-20,
ITS, and the Stanford Monitor.  However, it will also be capable of 
specialization for use with single processor S-1 configurations.  There
will also be some innovation in interactive user services.

A key problem to be solved is efficient allocation and scheduling of
resources.  It should be possible to flexibly allocate processors either
to a number of tasks supporting independent users or to separate forks
of a single task, depending on priorities.

The planning phase of this work (of about three months' duration)
will be devoted to the following tasks:
.bs
(1) familiarization with the S-1 equipment characteristics;

(2) characterization of the principal kinds of computing tasks that are to
be performed with this system;

(3) general design of program services to be provided by the operating
system, including primary memory allocation and file system
characteristics;

(4) general design of user services, including display control, command
languages, and character set standards;

(5) analysis of other resource allocation issues;

(6) study of major existing operating systems to determine which of their
features may be profitably included in the one to be created, and which,
if any, of their major modules may be appropriately carried over into the
new operating system;

(7) formulation of criteria for selection of programming languages to be
used in major develop- ment tasks.
.end continue
This phase of the work will culminate with the generation of a
report documenting the results of performing these 7 tasks.

Other products of this phase will include an assortment of planning
documents and specific recommendations on equipment design issues, such
as how the disk storage units should be interfaced to the multiprocessor
system.

The subsequent design phase (of about six months' duration) will focus
on detailed design of the functional elements of the system, selection of
system programming languages, programming of developmental tools (e.g., 
simple editors and debuggers), and possibly the modification of a
compiler to produce S-1 code.

.ss Crossbar Switch Design

It is proposed to design a crossbar switch to connect 16 S-1 processors
with 16 memory modules with a maximum concurrency of 16, and a throughput of
70 nanoseconds per word, as specified in Reference 1.
The switch will contain logic to allow an LSI-11 
processor, connected through an LLL-supplied parallel interface, to perform
comprehensive testing of the switch (both by providing artificial stimuli
to the switch, and by reading the state of switch buses and signals) and to
recover from what are considered to be probable recoverable failure modes of
the switch, processors, and memory modules.

SAIL proposes to perform the following subtasks of this basic task
during the current proposal period:
.bs
1) Familiarization of SAIL design personnel with the S-1 Design System.

2) Complete logical design of the switch using the S-1 Design System
Graphics Language.

3) Complete physical design of the switch, including layout and cable
assignment.

4) Production of final wire-lists through the S-1 Design System.

5) Debugging, including demonstration of full switch functionality, using
the LLL-supplied LSI-11 diagnostic system.

6) Documentation, including a structured text description of the hardware
to augment the structured drawings, and a high-level description of switch
operation.
.end

All aspects of crossbar switch hardware implementation is proposed
to be the responsibility of LLL.  At the completion of Step 4 (above), it
is proposed that LLL will construct the switch, associated cabinetry, and
LSI-11 debug processor, and will thereupon make the switch available for
debugging by SAIL staff.
Throughout the design, cognizant SAIL staff members will maintain
close contact with cognizant LLL staff members.

.s Facilities

Much of the planning and preliminary programming work on both projects
will be performed on the existing computer facilities of the Stanford
Artificial Intelligence Laboratory.  Since this equipment has already been
purchased, mostly with U. S. Government research funds, the only costs
involved in its use will be the support of part of a computer technician
and a share of other maintenance costs.

It is proposed that LLL make available to the Stanford Artificial
Intelligence Laboratory fractions of the capabilities of both single
processor and multiprocessor S-1 configurations appropriate to various
phases of advanced operating systems development and debugging.  Determination
of how this is to be most effectively accomplished is to be made
jointly by cognizant LLL and SAIL personnel, as such needs evolve.  It is
anticipated that some phone line access to LLL-based S-1 hardware
configurations will be needed and a budget item to support such access is
included.

.s Coordination and Reporting

It is proposed that primary coordination between cognizant LLL and SAIL
staff members be accompished via monthly meetings, to be conducted for
approximately half-day periods.  Senior SAIL
Project members will document the salient topics addressed at these 
conferences (including accomplishments of the previous month, and the
relatively detailed work plan for the upcoming month) and distribute such
documents to all cognizant SAIL and LLL staff members as the primary project
coordination papers.

SAIL proposes to submit two interim technical reports to LLL dealing
with the progress made during the Winter and Spring Quarters of 1978, and a
final, comprehensive report which treats in detail all aspects of the work
done during the January-September, 1978, period.  It is anticipated that the
Winter Quarter document will report the results of the 7-point operating
sysem planning phase discussed in Section 2.1, as well as the first three
items of the crossbar switch development discussed in Section 2.2.  It is
likewise expected that the Spring Quarter document will report preliminary
results of the operating system design phase of Section 2.1, and will also
report successful completion of at least 2 of the final 3 items of the switch
development of Section 2.2.  The final report will detail the design of the
operating system of Section 2.1, and will include the description of the
switch design implementation and debugging work of Section 2.2.  All these
reports will be delivered to LLL within 30 days of the end of the periods on
whose results they report.

.app SAIL Background in System Development

While the primary interests of the Stanford Artificial Intelligence
Laboratory have been in artificial intelligence, mathematical
theory of computation, and related theoretical problems, certain members
of the SAIL staff have been involved for many years in the development of
timesharing systems, programming languages, and interactive facilities.
Some of these activities are outlined below.

The concept of a general purpose timesharing system was first proposed by
John McCarthy when he was at MIT [2].  That proposal led to the pioneering
systems developed in Project MAC.  McCarthy also participated in the
development of an early timesharing system at BBN [3].

Shortly after arriving at Stanford in 1962, McCarthy undertook the development
of the first display-oriented timesharing system [4], based on a PDP-1 computer
with 12 displays and a link to an IBM 7090.  One notable accomplishment of
this project was the development of a "page editor" called TVEDIT that
exploited the capabilities of displays in text editing.  This was the forerunner
of screen editors now in use at SAIL and in a number of other advanced timesharing
systems.

When the SAIL computer facility was assembled in 1966, the staff of the PDP-1
timesharing project became the nucleus of the computer system staff that
developed a display-oriented system on a DEC PDP-6 computer initially and
later on KA10 and KL10 processors.
There are currently 70 display terminals connected to the system, most of
them with full graphics capability [5, 6].  There is also a connection to
the Arpanet, permitting remote access to and from hundreds of other
computers around the world.
In addition to providing conventional timesharing services, this system
handles realtime control of mechanical arms and television cameras, in
support of research in automatic mechanical assembly and computer vision [7].

In the period 1970-73, SAIL staff members designed a high speed processor
known as "Super Foonly", which featured a cache memory, user-accessible
microcode, and a "console computer" (a minicomputer that monitors the main
processor).  The latter innovation has since been included in a number of
other machines, including the S-1.
After the design was completed, it was made available to Digital Equipment
Corporation, which used it as the basis for their Decsystem/10 and Decsystem/20
computer systems.
The KL10 processor now at SAIL was donated by DEC out of gratitude for the
design contribution.

Another important outgrowth of this computer design project was a design
automation system known as SUDS [8], which combined interactive drawing
facilities with other computer-aided design services.
This was the first system that permitted a designer, working through a display
terminal, to completely design complex digital devices, including printed
circuit boards and backpanel wiring.
The system automatically produces artwork for PC boards and control tapes for
automatic wiring machines.
SUDS has been used to design five large computers so far, as well as
countless other digital devices.
It is currently in use at MIT, Carnegie-Mellon University, and
Digital Equipment Corporation, among other places, and is the basis of the
S-1 Design System.

Other interests of the SAIL staff include the development of
assemblers [9], the LISP family of programming languages and systems [10, 11, 12],
the SAIL language and compiler [13], text editors [14, 15], interactive
debuggers [16], document compilers [17], and computer communication systems [18].

The backgrounds of the individuals who will carry out the proposed work are
as follows.
John McCarthy, who will provide overall direction of the project,
is a Professor of Computer Science and Director of SAIL.
He has 26 years experience as a faculty
member at a number of major universities and has been a principal innovator
in artificial intelligence, mathematical theory of computation, and timesharing
systems.
Les Earnest, who is Associate Director of SAIL, will handle much of the
management of the project.  He has 24 years experience in programming, computer
system design and technical management.

Jeff Rubin, who will head the operating system design effort, is currently
in charge of system programming at SAIL and has twelve years experience as
a programmer, including six years as a system programmer at MIT and four
years in this capacity at SAIL.
Ted Panofsky, who will design the crossbar switch, is head of the SAIL
Computer Facility group, has been a design engineer at SAIL for ten years,
and had several years of electronics experience before that.
Martin Frost has been a systems programmer at SAIL for five years.

.bib;
⊗  Tom McWilliams and Curt Widdoes, "The S-1 Memory Interface",
October 3, 1977.

⊗  John McCarthy, "A Time Sharing Operator Program for our Projected IBM 709",
memo to P. M. Morse, MIT, January 1, 1959.

⊗  John McCarthy, S. Boilen, E. Fredkin, J.C.R. Licklider, "A Time-sharing
Debugging System for a Small Computer", <Proc. AFIP Conf.> (SJCC), Vol. 23,
1963.

⊗  John McCarthy, D. Brian, G. Feldman, J. Allen, "THOR -- A Display Based
Time-sharing System", <Proc. AFIPS Conf.> (FJCC), Vol. 30, Thompson,
Washington, D.C., 1967.

⊗  Brian Harvey and Martin Frost, "Monitor Command Manual", SAILON-54.5,
January 1976.

⊗  McCarthy, John, Lester Earnest, D. Raj. Reddy, Pierre Vicens, "A
Computer with Hands, Eyes, and Ears", <Proc. AFIPS Conf.> (FJCC),
1968.

⊗  Martin Frost, "UUO Manual", SAILON-55.5, October 1977.

⊗  Richard Helliwell, "Stanford Drawing Program", SAIL Program Note, 1971.

⊗  Fred Wright and Ralph Gorin, "FAIL", AIM-226, April 1974.

⊗  John McCarthy, "Recursive Functions of Symbolic Expressions", <Communications
of the ACM>, April 1960.

⊗  John McCarthy, <et al, LISP 1.5 Programmer's Manual,>, MIT Press, 1962.

⊗  David C. Smith, "MLISP User's Manual", AIM-84, January 1969.

⊗  John Reiser (ed.), "SAIL", AIM-289, August 1976.

⊗  William Weiher and Steve Savitzky, "Son of Stopgap", SAILON-50.3, October 1970.

⊗  Arthur Samuel and Martin Frost, "E Text Editor", Program Note, December 1977.

⊗  Phil Petit, "RAID", SAILON-58.1, February 1970.

⊗  Larry Tesler, "PUB, the Document Compiler", SAILON-70, September 1970.

⊗  John McCarthy and Les Earnest, "DIALNET and the Home Terminal", <Proc.
Computer Faire>, San Francisco, 1977.

.end
.next page; s Budget
.skip; once center
Nine Months Beginning 1 January 1978
.begin "bud"
.nofill
.turn on "α∂→\{"; tabs 32;
.			<< put commas in INCR and print it >>
.at "!" incr "∞"	⊂
.  if incr≤0 then sal←"" else sal←incr[∞-2 to ∞]; digs←incr/1000;
.  while("digs>0",|sal←digs[∞-2 to ∞]&","&sal; digs←digs/1000;|);
.  sal;
.  ⊃
.macro subtot	⊂
→_______
. ⊃
.macro percent(num)	⊂(((num+50)/100)&"α%")⊃;
.
.tot←0;		<< total costs >>
.
.				<< salary = semi*18  >>
.at "@" semi "," mo "." frac "∞"	⊂
. annual←(semi*(mo*10+frac)*101+250)/500;	tot←tot+annual;
→mo.frac\ →!annual∞
. ⊃
.at "#" amt "∞"	⊂ val←amt; tot←tot+val;
→!val∞
.  ⊃

→%3Person\
→Months\
%3A. Salaries and Wages%1

   1. Senior Personnel:

      a. John McCarthy @1683,0.6∞
	 Prof. of Computer Science
	 5α% acad. yr., 10α% summer

      b. Lester Earnest @1525,1.4∞
	 Senior Research Associate
	 15α%

   2. Other Personnel:

      a. Jeff Rubin @963,9.0∞
	 Computer Systems Spec.

      b. Ted Panofsky @825,8.1∞
	 Design Engineer, 90α%

      c. Martin Frost @700,9.0∞
	 Systems Programmer

      d. ------ @900,9.0∞
	 Systems Programmer

      e. Student Res. Assist. @477,6.0∞
	 50α% acad. yr., 100α% sum.

      f. Support Personnel:

	 (1) Secretary (25α%) @400,2.3∞

	 (2) Elect. Tech. (25α%) @550,2.3∞
.subtot
      Total Salaries & Wages →!tot∞

%3B. Staff Benefits%1 #(tot*1914+5000)/10000∞
     19.0α% till 1 Sept.'78,
     20.3α% thereafter
.subtot
%3C. Total Salaries, Wages,
     and Staff Benefits%1 →!tot∞

%3D. Permanent Equipment%1 →- - -

%3E. Expendable Supplies &%1 #1200∞
     %3Equipment (e.g. office
     supplies, copying, postage)%1

%3F. Travel%1 (domestic) #2000∞

%3G. Publications%1 #600∞

%3H. Other Costs%1 #1635∞
   1. Telephone →810\
   2. Computer Equipment
      Maintenance →825\
.subtot
%3I. Total Direct Costs%1 (A thru H) →!tot∞

%3J. Indirect Costs%1 #(tot*58 +50)/100∞
     (58α% of A thru H less D)
.subtot
.tty←"Total="&tot;
%3K. Total Costs →!tot∞

.end "bud"